package SubjectQueue;

import java.util.Deque;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Stack;

public class IsValid {

/**
 * 难度：简单
 * 
 * 20. 有效的括号
 * 	给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
 * 	有效字符串需满足：
 * 		左括号必须用相同类型的右括号闭合。
 * 		左括号必须以正确的顺序闭合。
 * 		注意空字符串可被认为是有效字符串。
 * 
 * 示例 1:
 * 	输入: "()"
 * 	输出: true
 * 
 * 示例 2:
 * 	输入: "()[]{}"
 * 	输出: true
 * 
 * 示例 3:
 * 	输入: "(]"
 * 	输出: false
 * 
 * 示例 4:
 * 	输入: "([)]"
 * 	输出: false
 * 
 * 示例 5:
 * 	输入: "{[]}"
 * 	输出: true
 * 
 * */
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		IsValid iv = new IsValid();
		System.out.println(iv.isValid1("()[]{}"));
	}
	//自己写
	public boolean isValid(String s) {
		Stack<Character> stack = new Stack<>();
		for(int i=0;i<s.length();i++) {
			if(s.charAt(i)=='(')stack.push(')');
			else if(s.charAt(i)=='{')stack.push('}');
			else if(s.charAt(i)=='[')stack.push(']');
			// 第三种情况：遍历字符串匹配的过程中，栈已经为空了，没有匹配的字符了，说明右括号没有找
			// 到对应的左括号 return false
			// 第二种情况：遍历字符串匹配的过程中，发现栈里没有我们要匹配的字符。所以return false
			else if(stack.isEmpty() || s.charAt(i)!=stack.peek()) {
				return false;
			}else stack.pop();// st.top() 与 s[i]相等，栈弹出元素

		}
		// 第一种情况：此时我们已经遍历完了字符串，但是栈不为空，说明有相应的左括号没有右括号来匹配，
		// 所以return false，否则就return true
		return stack.isEmpty();
    }
	//方法一：栈
	public boolean isValid1(String s) {
        int n = s.length();
        if (n % 2 == 1) {
            return false;
        }

        Map<Character, Character> pairs = new HashMap<Character, Character>() {{
            put(')', '(');
            put(']', '[');
            put('}', '{');
        }};
        Deque<Character> stack = new LinkedList<Character>();
        for (int i = 0; i < n; i++) {
            char ch = s.charAt(i);
            //如果遇到右括号就进入比较
            if (pairs.containsKey(ch)) {
            	//如果栈为空 或者 栈里的括号不等于pairs里的值则返回false
                if (stack.isEmpty() || stack.peek() != pairs.get(ch)) {
                    return false;
                }
                stack.pop();
            } else {
            	//左括号全部从这里入栈
                stack.push(ch);
            }
        }
        return stack.isEmpty();
    }
}
